The invention relates generally to computer graphics, and more particularly to free-form modeling of renderable objects.
A number of graphical user interfaces (GUI) for modeling three-dimensional objects are known. For instance, xe2x80x9cSketchxe2x80x9d is an interface designed to help a user with geometric modeling, see Zeleznik et al., xe2x80x9cSketch: An Interface for Sketching 3D Scenes,xe2x80x9d Proceedings of SIGGRAPH-96, 1996. Sketch uses a system of intuitive guesses to guide the user through geometrical model generation. For example, if the user draws three line segments meeting at one point and parallel to the projections of the x-, y- and z-axes of the scene, then Sketch generates a parallelepiped whose dimensions are determined by the lengths of the line segments. After the user has mastered a set of agreements like that, more complex models composed of many primitives can be generated.
Another system can be used for sketching CAD-like geometric objects, see Lipson et al., xe2x80x9cConceptual design and analysis by sketching,xe2x80x9d Proceedings of AIDAM-97, 1997. In an input sketch, the user draws both visible and hidden contours of a rectilinear object from which its shape is inferred. Their approach is based on correlations among arrangements of lines of the 2D drawing and lines in 3D space. For instance, by experimentation, the user can notice that the more two lines are parallel in the 2D sketch plane, the more the lines are likely to represent parallel lines in 3D space. They rely on a geometric correlation hypothesis that one can evaluate the likelihood of human understanding of the sketch by a joint probability of all correlations in the sketch.
Igarashi et al. also describe an interface for free-form modeling, see Igarashi et al. xe2x80x9cTeddy: A sketching interface for 3D freeform design,xe2x80x9d Proceedings of SIGGRAPH 99, pp. 409-416, 1999. There, the user inputs a simple closed stroke to form a contour. The system then generates a model in the form of a polygon mesh that matches the contour. The user adds details by editing the polygon mesh. Operations such as extrusion, cutting, bending and drawing on the mesh are allowed. However, because the underlying surface representation is a polygonal mesh, maintaining a smooth surfaced model is a problem.
Tolba et al. describe a system that allows the user to draw a scene with 2D strokes, and then to view the scene from different points of view as if a 3D scene was generated. The system projects the 2D strokes onto a sphere having its center at the viewing frustum. The strokes can then be rendered in perspective. The purpose of their system is to provide perspective drawing and not a 3D model of a scene, see Tolba et al., xe2x80x9cSketching with projective 2d strokes,xe2x80x9d ACM Symposium on User Interface Software and Technology, pp. 149-157, 1999, and Tolba et al., xe2x80x9cA projective drawing system,xe2x80x9d I3D""01, pp. 25-34, 2001.
Another system correlates features in a hand-drawn figure to a textured, 3D model. The 3D model is then distorted with a warp to conform to the hand-drawn figure. The warp distorts the model in two dimensions to match the figure from a given camera perspective, yet preserves 3D effects, such as self-occlusion and foreshortening, see Petrovic, xe2x80x9cShadows for cel animation,xe2x80x9d Proceedings of SIGGRAPH 2000,xe2x80x9d pp. 511-516, 2000.
With respect to underlying model representations, implicit-surface modeling is described by Bloomenthal, in xe2x80x9cIntroduction to Implicit Surfaces,xe2x80x9d Morgan-Kaufmann, 1997.
The xe2x80x9cSkinxe2x80x9d system supports a form of constructive drawing. There, the user generates a set of basic forms over which a skin is placed. The characteristics of the forms are then modified by small adjustments to offset distances at various scales of subdivision of the skin mesh. The skin is basically a polygonization of an implicit surface that is defined by a combination of signed-distance representations of the underlying forms, see Markosian, xe2x80x9cSkin: A constructive approach to modeling free-form shapes,xe2x80x9d Proceedings of SIGGRAPH 99, pp. 393-400, 1999.
In contrast, Wyvill et al. describe a blob-tree. The blob-tree is a CSG like hierarchy of implicit models in which implicit shapes are combined by a rich collection of operators, including various deformation operators. The emphasis in that work is on the representation of complex implicit surfaces through a tree-like structure, see Wyvill et al., xe2x80x9cThe Blob Tree, Warping, Blending and Boolean Operations in an Implicit Surface Modeling System,xe2x80x9d Implicit Surfaces 3, 1998.
Barthe et al. describe a method for blending a pair of implicit surfaces defined as zero-sets of functions ƒand g by considering each point of R3 as having ƒand g xe2x80x9ccoordinates,xe2x80x9d i.e., by treating a mapping
a. (ƒ, g):R3:xe2x86x92R2:pxe2x86x92(ƒ(p), g(p))
as a xe2x80x9ccoordinatizationxe2x80x9d of 3D space. A first surface is a pre-image of the ƒ=0 axis, and a second is the pre-image of the g=0 axis. By examining pre-images of other curves in (ƒ, g)-space, especially ones containing large portions of these two axes, they can blend between the two surfaces, see Barthe et al., xe2x80x9cImplicit extrusion fields,xe2x80x9d The 2000 International Conference on Imaging Science, Systems, and Technology (CISST""2000), pp. 75-81, 2000.
Variational implicit surfaces are described by Turk et al., in xe2x80x9cShape transformation using variational implicit functions,xe2x80x9d SIGGRAPH""99, 1999. Variational implicit surfaces can be used to represent complex objects, as described by Carr et al. in xe2x80x9cReconstruction and representation of 3d objects with radial basis functions,xe2x80x9d Proceedings of SIGGRAPH 2001, pp. 67-76, 2001. Their methods allows one to simplify model representations by judicious deletion of constraint points.
The present invention uses variational implicit surfaces to support a set of free-form modeling operations. The modeling operations are inflation, hierarchy generation, merging, and modification. The inflation, merging and modification operations are implemented in a similar way by removing some constraints on the variational implicit surface and introducing others. This uniformity leads to simplicity of system structure and process coding.
More particularly, an input device is used to generate input strokes visible on a display device. The input strokes are acquired and resampled to be evenly spaced. Then, depth values are assigned to the resampled 2D points to form 3D contours. Variational implicit surfaces are fitted to the 3D contours to generate 3D blobs that form the 3D model to be rendered on an output device. The blobs can be merged by guidance strokes, and modified by target strokes.